﻿using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;

namespace BaseThing
{
    public class GeometryFactory
    {
        public static List<List<Vector2>> EarClip(CircularList<Vector2> vertices)
        {
            List<List<Vector2>> ears;
            CircularListNode<Vector2> node1, node2;
            bool isEar;

            ears = new List<List<Vector2>>();

            node1 = vertices.first;
            while (node1.previous.previous != node1.next)
            {
                isEar = (InternalAngle(ref node1.previous.value, ref node1.value, ref node1.next.value) <= Math.PI);

                if (isEar)
                {
                    node2 = node1.next.next;
                    while (node2 != node1.previous)
                    {
                        if (PointInsideTriangle(ref node2.value,
                                               ref node1.previous.value, ref node1.value, ref node1.next.value))
                        {
                            isEar = false;
                            break;
                        }

                        node2 = node2.next;
                    }

                    if (isEar)
                    {
                        ears.Add(new List<Vector2> { node1.previous.value, node1.value, node1.next.value });

                        node2 = node1.next;
                        vertices.Remove(node1);
                        node1 = node2;
                    }
                }

                if (!isEar)
                {
                    node1 = node1.next;
                }
            }

            ears.Add(new List<Vector2> { node1.previous.value, node1.value, node1.next.value });

            return ears;
        }

        private static float InternalAngle(ref Vector2 v1, ref Vector2 v2, ref Vector2 v3)
        {
            Vector2 a, b;
            float angle;

            a = v2 - v1;
            b = v3 - v2;

            angle = (float)Math.Atan2(b.Y, b.X) - (float)Math.Atan2(a.Y, a.X);
            if (angle < 0)
            {
                angle += (float)Math.PI * 2;
            }

            return angle;
        }

        private static bool PointInsideTriangle(ref Vector2 p, ref Vector2 a, ref Vector2 b, ref Vector2 c)
        {
            Vector2 v0, v1, v2;
            float dot00, dot01, dot02, dot11, dot12,
                  invDenom, u, v;

            // Compute vectors        
            v0 = c - a;
            v1 = b - a;
            v2 = p - a;

            // Compute dot products
            Vector2.Dot(ref v0, ref v0, out dot00);
            Vector2.Dot(ref v0, ref v1, out dot01);
            Vector2.Dot(ref v0, ref v2, out dot02);
            Vector2.Dot(ref v1, ref v1, out dot11);
            Vector2.Dot(ref v1, ref v2, out dot12);

            // Compute barycentric coordinates
            invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
            u = (dot11 * dot02 - dot01 * dot12) * invDenom;
            v = (dot00 * dot12 - dot01 * dot02) * invDenom;

            // Check if point is in triangle
            return (u > 0) && (v > 0) && (u + v < 1);
        }
    }
}